//
// Created by ASUS on 2024/12/10/星期二.
//
#include <bits/stdc++.h>
using namespace std;


class LinkCutTree {
	struct Node{
		int l,r;
		int s=0;
		int lazy=0;
	};
public:
	//x的父亲，x的深度，x的子树大小，x的重儿子
	vector<int> fa,dep,size,son;
	//x 所在重链的顶部节点（深度最小）， x 的 DFS 序，也是其在线段树中的编号，DFS 序所对应的节点编号，有 rnk(dfn(x))=x。
	vector<int> top, dfn, rnk,w_new;

	vector<Node> t;

	int cnt=0;
	LinkCutTree(vector<vector<int>>&g,vector<int>&w){
		int n=g.size();
		fa.resize(n);
		dep.resize(n);
		size.resize(n);
		son.resize(n);
		top.resize(n);
		dfn.resize(n);
		rnk.resize(n);
		t.resize(4*n);
		w_new.resize(n);
		dfs1(1,0,g);
		dfs2(1,1,g,w);
		build(1,1,n);
	}

	void dfs1(int x,int father,vector<vector<int>>&g) {
		dep[x]=dep[father]+1;
		fa[x]=father;
		size[x] = 1;
		for(int y:g[x]){
			if(y!=father){
				dfs1(y,x,g);
				size[x]+=size[y];
				if(son[x]==0 || size[y]>size[son[x]]) son[x]=y;
			}
		}
	}

	void dfs2(int x, int topx,vector<vector<int>>&g,vector<int>&w) {
		dfn[x] = ++cnt;
		w_new[cnt]= w[x];
		top[x] = topx;
		rnk[cnt] = x;
		if (son[x] == 0) return;
		dfs2(son[x], topx,g,w);  // 优先对重儿子进行 DFS，可以保证同一条重链上的点 DFS 序连续
		for(int y:g[x]){
			if(y!=son[x]&&y!=fa[x]){
				dfs2(y,y,g,w);
			}
		}
	}

	void pushup(int i){
		t[i].s=t[2*i].s+t[2*i+1].s;
	}

	void pushdown(int i){
		if(t[i].lazy){
			t[2*i].lazy+=t[i].lazy;
			t[2*i].s+=1ll*t[i].lazy*(t[2*i].r-t[2*i].l+1);
			t[2*i+1].lazy+=t[i].lazy;
			t[2*i+1].s+=1LL*t[i].lazy*(t[2*i+1].r-t[2*i+1].l+1);
			t[i].lazy=0;
		}
	}

	void build(int i,int l,int r){
		t[i].l=l;
		t[i].r=r;
		if(l==r){
			t[i].s=w_new[l];
			return;
		}
		int mid=l+(r-l)/2;
		build(2*i,l,mid);
		build(2*i+1,mid+1,r);
		pushup(i);
	}

	int query(int i,int l,int r){
		if(t[i].l>r||t[i].r<l) return 0;
		if(t[i].l>=l&&t[i].r<=r){
			return t[i].s;
		}
		pushdown(i);
		return query(2*i,l,r)+query(2*i+1,l,r);
	}

	void update(int i,int l,int r,int v){
		if(t[i].l>r||t[i].r<l) return ;
		if(t[i].l>=l&&t[i].r<=r){
			t[i].lazy+=v;
			t[i].s+=v*(t[i].r-t[i].l+1);
			return;
		}
		pushdown(i);
		update(2*i,l,r,v);
		update(2*i+1,l,r,v);
		pushup(i);
	}
	//x到y的最短路径上的点加v
	void update_range(int x,int y,int v){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]]) swap(x,y);
			update(1,dfn[top[x]],dfn[x],v);
			x=fa[top[x]];
		}
		if(dep[x]>dep[y]) swap(x,y);
		update(1,dfn[x],dfn[y],v);
	}
	//x到y的最短路径上的点的和
	int query_range(int x,int y){
		int res=0;
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]]) swap(x,y);
			res+=query(1,dfn[top[x]],dfn[x]);
			x=fa[top[x]];
		}
		if(dep[x]>dep[y]) swap(x,y);
		res+=query(1,dfn[x],dfn[y]);
		return res;
	}
	//x的子树所有节点加v
	void update_tree(int x,int v){
		update(1,dfn[x],dfn[x]+size[x]-1,v);
	}
	//x的子树所有节点的和
	int query_tree(int x){
		return query(1,dfn[x],dfn[x]+size[x]-1);
	}

	//求最近公共祖先
	int lca(int u, int v) {
		while (top[u] != top[v]) {
			if (dep[top[u]] > dep[top[v]])
				u = fa[top[u]];
			else
				v = fa[top[v]];
		}
		return dep[u] > dep[v] ? v : u;
	}
};